public class test02 {
    class Solution {
        List<List<Integer>> res;
        List<Integer> list;
        int sum;
        public List<List<Integer>> combinationSum3(int k, int n) {
            sum = 0;
            res = new ArrayList<>();
            list = new ArrayList<>();
            backTracking(k,n,1);
            return res;
        }
        private void backTracking(int k,int n,int begin){
            //已经大于，不用往下回溯了
            if(sum>n){
                return;
            }

            if(sum==n && k==list.size()){
                res.add(new ArrayList(list));
                return;
            }
            for(int i = begin;i<=9-(k-list.size())+1;i++){
                sum += i;
                list.add(i);
                backTracking(k,n,i+1);
                list.removeLast();
                sum -= i;
            }
        }
    }
}
